In graph theoretical models of the spread of disease through populations, thespread of opinion through social networks, and the spread of faults throughdistributed computer networks, vertices are in two states, either black orwhite, and these states are dynamically updated at discrete time stepsaccording to the rules of the particular conversion process used in the model.This paper considers the irreversible k-threshold and majority conversionprocesses. In an irreversible k-threshold (resp., majority) conversion process,a vertex is permanently colored black in a certain time period if at least k(resp., at least half) of its neighbors were black in the previous time period.A k-conversion set (resp., dynamic monopoly) is a set of vertices which, ifinitially colored black, will result in all vertices eventually being coloredblack under a k-threshold (resp., majority) conversion process. We answerseveral open problems by presenting bounds and some exact values of the minimumnumber of vertices in k-conversion sets and dynamic monopolies of completemultipartite graphs, as well as of Cartesian and tensor products of two graphs.
展开▼
